/*
    汉诺塔(分治算法)
 */
public class Hanoi {
    public static void main(String[] args) {
        hanoiTower(4,'A','B','C');
    }

    /**
     * 分治算法解决汉诺塔问题
     * @param num 汉诺塔盘数
     * @param a 每次递归的起始位置
     * @param b 每次递归的暂留位置
     * @param c 每次递归的目标位置
     */
    public static void hanoiTower(int num,char a,char b,char c){
        if (num == 1){
            System.out.println("第1个盘从 "+a+"移动到"+c);
        } else {
            //两个盘及以上的移动策略
            //最底层上面所有盘为一个整体，从起始位置移动到暂留位置
            hanoiTower(num-1,a,c,b);
            //最底层盘，从起始位置移动到目标位置
            System.out.println("第"+num+"个盘从 "+a+"移动到"+"c");
            //将上面所有盘的整体，由暂留位置移动到目标位置
            hanoiTower(num-1,b,a,c);
        }
    }
}
